home *** CD-ROM | disk | FTP | other *** search
/ Creative Computers / Creative Computers CD-ROM, Volume 1 (Legendary Design Technologies, Inc.)(1994).iso / shareware / fractals / mandelsquare / mandelsquare-1.06.lha / skip.c < prev    next >
C/C++ Source or Header  |  1992-10-12  |  13KB  |  538 lines
  1. /***************************************************************************
  2. *
  3. *  This contains routines to compress images one of two ways:
  4. *      1. Vertical Byte Run Length (VRUN)
  5. *      2. Vertical Byte Run Length With Skips (SKIP)
  6. *   from amiga/programs #274, dated jul 8 1987...
  7. *
  8. * The routines here compress a single bit-plane.  There's routines to
  9. * see how big the compressed result will be (xxxx_count_plane() )
  10. * and routines to actually compress the result into a buffer in memory
  11. * (xxxx_comp_plane() )  where xxxx is either vrun or skip depending....
  12. *
  13. *
  14. * VRUN compression format:
  15. *    a VRUN-compressed plane is a concatenation of VRUN-compressed columns.
  16. *    Each column is an op-count followed by a concatenation of op-count op's.
  17. *    An op is in one of these two formats:
  18. *        SAME_OP:  1-byte-count  followed by 1-byte to repeat count times.
  19. *        UNIQ_OP:  1-byte-count  followed by count bytes of data to copy
  20. *    The counts in either op must be 127 or less.  If it's a UNIQ_OP the
  21. *    hi bit of the count op is set (it's masked with 127 to find the actual
  22. *    count).
  23. *
  24. * SKIP compression format:
  25. *    a SKIP compressed plane is a concatenation of SKIP-compressed columns.
  26. *    Like a VRUN this is an op-count followed by a concatenation of op;s.
  27. *    However in this one we have 3 op formats:
  28. *       SKIP_OP:  Hi bit clear.  Count of bytes to skip.
  29. *       UNIQ_OP:  Hi bit set.  Remainder is count of data to copy. Data
  30. *                 follows immediately.
  31. *       SAME_OP:  A zero followed by a one-byte-count followed by one byte
  32. *                 of data to repeat count times.
  33. *
  34. ****************************************************************************
  35. *
  36. * Small changes made for SAS/C by Olaf `Olsen' Barthel: added registerized
  37. * parameters and STATIC declarations to make it easier for the compiler to
  38. * inline certain routines.
  39. *                          -olsen
  40. *
  41. ***************************************************************************/
  42.  
  43. #include <exec/types.h>
  44. #include <graphics/gfx.h>
  45.  
  46. #define MAXRUN 127
  47.  
  48. static WORD linebytes = 40;
  49. static WORD uniq_count;
  50. static unsigned char *uniq;
  51. static WORD op_count;
  52.  
  53. UBYTE * __regargs    skip_comp_plane(UBYTE *in, UBYTE *last_in, UBYTE *out, WORD next_line, WORD rows);
  54. WORD __regargs        skip_count_plane(UBYTE *in, UBYTE *last_in, WORD next_line, WORD rows);
  55.  
  56. STATIC WORD        vskip(unsigned char *in, unsigned char *last_in, WORD count);
  57. STATIC WORD        vsame(unsigned char *in, WORD count);
  58. STATIC WORD        skip_count_line(unsigned char *in, unsigned char *last_in, WORD count);
  59. STATIC unsigned char *    flush_uniq(unsigned char *stuff);
  60. STATIC int        copy_line_to_chars(unsigned char *in, unsigned char *out, int linebytes, int count);
  61. STATIC unsigned char *    skip_comp_line(unsigned char *in, unsigned char *last_in, unsigned char *out, WORD count);
  62. STATIC WORD        vrun_count_line(unsigned char *in, WORD count);
  63. STATIC WORD        vrun_count_plane(unsigned char *in, WORD next_line, WORD rows);
  64. STATIC unsigned char *    vrun_comp_line(unsigned char *in, unsigned char *out, WORD count);
  65. STATIC unsigned char *    vrun_comp_plane(unsigned char *in, unsigned char *out, WORD next_line, WORD rows);
  66.  
  67. /* count up how many in a column are the same between in and last_in ...
  68.    ie how big of a "skip" can we go on. */
  69.  
  70. STATIC WORD
  71. vskip(in, last_in, count)
  72.      register unsigned char *in;
  73.      register unsigned char *last_in;
  74.      register WORD count;
  75. {
  76.     register WORD skips;
  77.  
  78.     skips = 0;
  79.     while (--count >= 0)
  80.     {
  81.     if (*in != *last_in)
  82.         break;
  83.     in += linebytes;
  84.     last_in += linebytes;
  85.     skips++;
  86.     }
  87.     return (skips);
  88. }
  89.  
  90. /* vsame() - count up how many in a row (vertically) are the same as the
  91.    first one ... ie how big of a "same" op we can have */
  92. STATIC WORD
  93. vsame(in, count)
  94.      register unsigned char *in;
  95.      register WORD count;
  96. {
  97.     register unsigned char c;
  98.     register WORD same;
  99.  
  100.     c = *in;
  101.     in += linebytes;
  102.     --count;
  103.     same = 1;
  104.     while (--count >= 0)
  105.     {
  106.     if (*in != c)
  107.         break;
  108.     same++;
  109.     in += linebytes;
  110.     }
  111.     return (same);
  112. }
  113.  
  114.  
  115. /* skip_count_line() - figure out what size this column will compress
  116.    to using vertical-byte-run-length-with-skips encoding */
  117. STATIC WORD
  118. skip_count_line(in, last_in, count)
  119.      register unsigned char *in;
  120.      register unsigned char *last_in;
  121.      WORD count;
  122. {
  123.     WORD local_count;
  124.     WORD a_run;
  125.     WORD run_length;
  126.     WORD uniq_count = 0;
  127.     WORD comp_count = 1;    /* one for the op count */
  128.  
  129.  
  130.     if (vskip(in, last_in, count) == count)    /* skip whole column? */
  131.     return (1);
  132.     for (;;)
  133.     {
  134.     if (count <= 0)
  135.         break;
  136.     local_count = (count < MAXRUN ? count : MAXRUN);
  137.     a_run = 0;
  138.     if ((run_length = vskip(in, last_in, local_count)) > 1)
  139.     {
  140.         count -= run_length;
  141.         if (count > 0)    /* the last skip disappears */
  142.         comp_count += 1;
  143.         a_run = 1;
  144.     }
  145.     else if ((run_length = vsame(in, local_count)) > 3)
  146.     {
  147.         count -= run_length;
  148.         a_run = 1;
  149.         comp_count += 3;
  150.     }
  151.     if (a_run)
  152.     {
  153.         in += run_length * linebytes;
  154.         last_in += run_length * linebytes;
  155.         if (uniq_count > 0)
  156.         {
  157.         comp_count += uniq_count + 1;
  158.         uniq_count = 0;
  159.         }
  160.     }
  161.     else
  162.     {
  163.         in += linebytes;
  164.         last_in += linebytes;
  165.         uniq_count++;
  166.         count -= 1;
  167.         if (uniq_count == MAXRUN)
  168.         {
  169.         comp_count += uniq_count + 1;
  170.         uniq_count = 0;
  171.         }
  172.     }
  173.     }
  174. /*  if (count != 0)
  175.     {
  176.         printf("weird end count %d in skip_line_count\n");
  177.     }*/
  178.     if (uniq_count != 0)
  179.     {
  180.     comp_count += uniq_count + 1;
  181.     }
  182.     return (comp_count);
  183. }
  184.  
  185. /* skip_count_plane() - figure out what size this plane will compress
  186.    to using vertical-byte-run-length-with-skips encoding */
  187.  
  188. /*
  189. WORD
  190. skip_count_plane(in, last_in, next_line, rows)
  191.      unsigned char *in;
  192.      unsigned char *last_in;
  193.      WORD next_line;
  194.      WORD rows;
  195. */
  196.  
  197. WORD __regargs
  198. skip_count_plane(UBYTE *in, UBYTE *last_in, WORD next_line, WORD rows)
  199. {
  200.     WORD i;
  201.     WORD comp_count;
  202.  
  203.     linebytes = next_line;
  204.     comp_count = 0;
  205.     i = next_line;
  206.     while (--i >= 0)
  207.     {
  208.     comp_count += skip_count_line(in, last_in, rows);
  209.     in++;
  210.     last_in++;
  211.     }
  212.     return (comp_count);
  213. }
  214.  
  215. /* flush_uniq() - write out the "uniq" run that's been accumulating while
  216.    we've been looking for skips and "same" runs. */
  217. STATIC unsigned char *
  218. flush_uniq(stuff)
  219.      unsigned char *stuff;
  220. {
  221.     if (uniq_count > 0)
  222.     {
  223.     op_count++;
  224.     *stuff++ = (uniq_count | 0x80);
  225.     copy_line_to_chars(uniq, stuff, linebytes, uniq_count);
  226.     stuff += uniq_count;
  227.     uniq_count = 0;
  228.     }
  229.     return (stuff);
  230. }
  231.  
  232. STATIC int
  233. copy_line_to_chars(in, out, linebytes, count)
  234.      unsigned char *in, *out;
  235.      int linebytes, count;
  236. {
  237.     while (count--)
  238.     {
  239.     *out = *in;
  240.     out++;
  241.     in += linebytes;
  242.     }
  243.     return (0);
  244. }
  245.  
  246. /* skip_comp_line() - Compress "in" into "out" using vertical-byte-run-
  247.    with-skips encodeing. Return pointer to "out"'s next free space. */
  248.  
  249. STATIC unsigned char *
  250. skip_comp_line(in, last_in, out, count)
  251.      register unsigned char *in;
  252.      unsigned char *last_in;
  253.      unsigned char *out;
  254.      WORD count;
  255. {
  256.     register unsigned char *stuffit;
  257.     WORD local_count;
  258.     WORD a_run;
  259.     WORD run_length;
  260.  
  261. /* if can skip over whole column, then compact a bit by just setting the
  262.    "op count" for this column to zero */
  263.     if (vskip(in, last_in, count) == count)    /* skip whole column? */
  264.     {
  265.     *out++ = 0;
  266.     return (out);
  267.     }
  268.  
  269.     op_count = 0;        /* haven't done any op's yet */
  270.  
  271. /* initialize variables which keep track of how many uniq bytes we've gone
  272.    past, and where uniq run started. */
  273.     uniq_count = 0;
  274.     uniq = in;
  275.  
  276.     stuffit = out + 1;        /* skip past "op-count" slot in out array */
  277.     for (;;)
  278.     {
  279.     if (count <= 0)
  280.         break;
  281.     local_count = (count < MAXRUN ? count : MAXRUN);
  282.     a_run = 0;        /* first assume not a skip or a same run */
  283.     /* see how much could skip from here.  Two or more is worth skipping! */
  284.     if ((run_length = vskip(in, last_in, local_count)) > 1)
  285.     {
  286.         a_run = 1;
  287.         count -= run_length;
  288.         stuffit = flush_uniq(stuffit);    /* flush pending "uniq" run */
  289.         if (count > 0)    /* last skip vanishes */
  290.         {
  291.         op_count++;
  292.         *stuffit++ = run_length;
  293.         }
  294.     }
  295.     /* four or more of the same byte in a row compresses